Copyright: ®1995 Philippe BASCIANO


Menu Principal
PegSolit™...

 English

 Français

 Italiano

 Español

 Deutsch

 Nederlands


English help main menu
English (Or something that looks like, a bit).

 Introduction, rules of the Peg Solitaire game

 Creating a particular configuration

 Playing by yourself

 Starting the search

 Giving up the search

 Modifying the parameters

 Saving and loading configurations

 Taking back, Cancelling the last move

 The four numbers at the top-right corner

 A very short history of the game

 Selective bibliography & other Peg Solitaire programs for Windows

 Various comments about the programming of this game

 Credits ! People I'd like to thank

If you want the last version of this game, send me a French FF20 bill or a US $5 bill (just for shipping & diskette). The Windows 95 version should be available before long (June 96). You will receive in the same time all my other games for Windows.


Introduction
Intoduction

The aim of the game is to remove the pegs from the board. You have to move the pegs by capturing them like in the Checkers. A capturing move is a jump and here, it is the only move allowed. The winning configuration is an empty board with one single peg (the final position doesn't matter).

There are several initial boards. The english, the french, the square, the egyptian, the aztec, and the hexa boards. The english board is the most famous, it is composed of 32 places. The french one is the same plus 4 pegs in the 4 angles. The egyptian and aztec boards are triangular boards (15 and 28 places). The hexa board follows the same rules that the two triangular ones. For each one of these boards, the empty starting place is arbitrary chosen. PegSolit™ solves particular configurations. You put the pegs on the board by yourself, and you start the search once you have the configuration that you wish.


Creation of a configuration
Creating a configuration :

You use the arrows or the numeric pad. (Up, Down, Right, Left, Page Down, Page Up, Home and End). You can move the cursor of the mouse on the board. To add a peg, press the insert key, to remove a peg, press del.

You can also use the mouse, click the left button to remove a peg, the right one to add a peg. If you press the F5,F6,F7,F8 function key, the program will load the saved classic configurations. If you press F9 or if you click on the Vacuum button, the board will be cleared.

Press the Rotation and Mirror buttons to rotate the board, or to get the symmetry.


Playing by yourself
Playing by yourself :

If you wish to solve the Solitaire by yourself, you can select a peg by clicking on it. Once you have clicked, you move it by keeping the button pressed, and you can drop it on an allowed place.

By the same way, you can select or drop a peg by pressing the space bar or the enter key. The peg under the mouse cursor will be selected if the place is full, or a peg will be created if the place is empty.

If you're playing on the egyptian or aztec board, you can move the pegs in diagonal.


Taking back
Taking Back :

Press F4.

Press BackSpace key.

Click on the Back ! button.

Click on the middle button of your mouse (if you have a three buttons one !) to get the first board.

Press Ctrl+left arrow to get the first board.

If you click on the right button of your mouse, or if you set a classic board, it will erase the saved configurations !


Save and load a solution
Save and Load :

When the xxx s processing or I'm so great dialog box appears, press the Save or Load button. If you wish to load a configuration directly, set 2 pegs besides each others, on an empty board, and launch the search !


The 4 numbers
The 4 numbers at the top right of the main dialog :

Top left : The number of pegs on the board.

Top right : The number of playable jumps.

Bottom Left : n, the first De Brujin's sum.

Bottom Right : m, the second De Brujin's sum.

The De Brujin's sums are constant for a given board, and keep their value if you move correctly a peg on the board. If you set one single peg on the board (where you like), these two sums are different from 0. So if one of this sum is equal to 0 at the beginning (when you set the complete board), you can say immediatly that there is no solution !

If you're interested in this theory, here is the source code translated into Pascal for the calculation of these sums (for the classic boards) :

CONST bs_table = 6; {nb of places - 1}

TYPE Solitaire = ARRAY[0..bs_table,0..bs_table] OF BOOLEAN;

{an array of places}

{(i,j) full if and only if A[i,j]}

CONST _plusG4 : ARRAY[0..3,0..3] OF BYTE {sum in G4 Group}

= ((0,1,2,3),

   (1,0,3,2),

   (2,3,0,1),

   (3,2,1,0));

FUNCTION De_Brujin_N(A : Solitaire) : BYTE; {Sum n}

VAR i,j : BYTE;

    som : BYTE;

BEGIN

 som := 0;

 FOR i := 0 TO bs_table DO

  FOR j := 0 TO bs_table DO

   IF (A[i,j]) THEN som := _plusG4[som,((i+j+2)MOD 3)+1];

 De_Brujin_N := som;

END;

FUNCTION De_Brujin_M(A : Solitaire) : BYTE; {Sum m}

VAR i,j : BYTE;

    som : BYTE;

BEGIN

 som := 0;

 FOR i := 0 TO bs_table DO

  FOR j := 0 TO bs_table DO

   IF (A[i,j]) THEN som := _plusG4[som,((i-j+6)MOD 3)+1];

 De_Brujin_M := som;

END;


Starting the search
Starting the search :

You just have to click on the Search button. If the program finds a solution, the xxx s processing box will show. And you can see all the moves you have made to reach the last board. The pogram can tell you that there is no solution, or in most of the cases, it will tell you that it has not found a solution, and you will have to modify the different parameters. If you have selected a depth greater than 10, you could have not enough memory to solve the problem. Click on the 386 extended icon of the configuration panel, or buy some RAM !.

But, *Generally* if there is a solution, PegSolit finds it, with a depth < 10.

Important note:

PegSolit prefers this configuration :

  ...                                ooo

  ...                                ooo

..o.o..                            ooooooo

ooo.ooo   to this configuration:   ooo.ooo

ooooooo                            ..o.o..

  ooo                                 ...

  ooo                                 ...

So choose the good symmetry ! Take care that it is better to select a configuration which pegs are in the bottom right corner to a configuration which pegs are in the top left one ! (Press the Rotation (keyboard : Alt+R or Ctrl+R) and Mirror (keyboard : Alt+Y or Ctrl+S) buttons !).


Giving up the search
Giving up the search :

Click on the Abort button. Be careful, if you wish to leave PegSolit™ (Alt+F4 function key, or Close item of the system menu) you must first give up the search, if the program is currently working.


Modify the depth
Modify the parameters :

By pressing the F3 function key you will have the Modify parameters dialog box. Be careful : If you use big depths (above 10), the time of search will increase a lot. The default depth is 0. This value is enough to solve the classic game of the english Solitaire. But, it won't be enough to find a solution if you're trying to solve other elaborated configurations. You must increase this value, and wait a bit more to find a solution or to know, may be, if there is'nt one.

You can change the pruning setting, if you're working with the deep pruning option this configuration :

  ...

  o..

.......

...oo..

..o....

  ...

  ...

will be eliminated, because the highest peg is far from the others.

Click on the Look button to set the board and the peg that you wish.

Click on the Solved button to see the saved boards.

The final positions drawing indicates where will be probably placed the last peg if there is a solution.

in red : the final positions.


A short history of the game
A short history of the game :

The first evidence of Peg Solitaire being played was in France in the late 1600s at the court of Louis XIV.  According to the legend, a prisoner who was jailed in La Bastille (1661-1666) may have invented the game. (Paul Pellisson-Fontainier ?). They used the 37-hole cross-shaped board, now referred to as the French board by those in the know.  However, the game is simple and was likely first played much, much earlier.  Liebniz mentioned it in a paper he wrote for the Berlin Academy in 1710, seeming quite enthusiastic about it.  Chevalier Louis de Jaucourt wrote a scholarly article about the game for a French encyclopedia in 1765 and J. C. Wiegleb published a mathematical study of the game, with solutions to some of the boards, in Germany in 1779.  The game has been played, studied and computer-analyzed ever since.

[Written by Rob Hafernik from his game Peg Solitaire for Newton©AppleComputerRubish]


Various comments
Various comments :

On a DX 25 Mhz 386,  RAM 4 Mo (Configuration on which the program has been created), the program solves the classic configuration of the english Solitaire in 10s, with a depth equal to 0, in the deep pruning mode. The french Solitaire is solved in 12s with the same parameters. With a pentium or a 486 DX2 66/80 or DX4 80/100, it might take less than 1 or 2 seconds !

To create the 3D controls, I used the Microsoft ctl3d.dll library. To save the configrations on the .ini file I used the Microsoft commctrl.dll library. (Thanks to CHRISTOPHE MAGIN PRIART, for his article published in Pascalissime, a french Pascal programming review).

If you find any bugs in the program, or wish to make comments or suggestions, please write me. This program is freeware, you can use and distribute it freely, but can't modify it in any way.

PHILIPPE BASCIANO, June, 30th, 1994, 21h30.


Credits
Credits :

hey hey, my my, let's read a few french words !


Index en langue française
Français

 Introduction, règles du jeu de Solitaire

 Créer une configuration particulière

 Jouer manuellement

 Lancer la recherche automatique

 Abandonner la recherche

 Modifier les paramètres de recherche

 Annuler le dernier mouvement

 Sauver et charger une configuration

 Les quatre afficheurs numériques

 Une petite bibliographie sélective

 Bref historique du jeu du solitaire

 Remerciements et redevances

 Quelques remarques diverses

Si vous souhaitez recevoir la dernière version de ce jeu, envoyez moi un billet de 20 Fr Français ou un billet de 5$ US (juste pour le port et la disquette). La version Windows 95 devrait être disponible d'ici peu (J'espère d'ici Juin 96). Vous recevrez en même temps tous mes autres jeux pour Windows.


Introduction

Le but du jeu est de se débarrasser des fichets figurant sur le plateau. Vous devez déplacer les fichets (par prise successive comme au jeu de Dames), la prise étant ici le seul et unique mouvement autorisé. La configuration gagnante est le plateau vide, exceptée une case contenant un fichet. Cette case est quelconque sur le plateau.

Il existe plusieurs tableaux initiaux, les tableaux français, anglais, carré, égyptien, aztèque et hexa. Le tableau anglais est le plus couramment représenté, il se compose de 32 fichets. Le tableau français est identique avec en plus 4 fichets disposés aux 4 angles. Les tableaux égyptien et aztèque, que j'ai dénommé ainsi parcequ'ils représentent une pyramide, se composent de 15 et 28 fichets. Le tableau hexa suit les mêmes règles de déplacement que ses confrères triangulaires. Leur particularité est que l'on peut se déplacer en diagonal. PegSolit™ permet la résolution de configurations particulières : vous disposez vous-même les fichets sur les cases, et vous lancez la  recherche une fois obtenue la configuration que vous souhaitiez.


Création d'une configuration
Créer une configuration :

Pour cela vous disposez des flèches directionnelles (Haut, Bas, Page Down, Page Up, Home et Fin) qui vous permettent de déplacer le curseur de la souris sur le tableau du Solitaire. Pour ajouter un fichet, appuyez sur la touche Insert, pour supprimer un fichet sur la touche Suppr.

Vous pouvez tout aussi bien tout créer à la souris (bouton droit pour positionner un fichet ou pour en enlever un). Les contrôles claviers ne sont programmés que pour les cas des Solitaires français et anglais.

En particulier, vous pouvez partir des configurations classiques (anglaise, française, égyptienne ou aztèque). Presser les touche F5, F6, F7,F8 a pour effet de charger les configurations classiques. Pressez F9 ou cliquer sur le bouton Vacuum pour vider le tableau de tous ses fichets.

Pressez les boutons Rotation ou Mirror pour obtenir les configurations symétriques.


Jouer manuellement
Jouer manuellement :

Si vous le désirez, vous pouvez vous entraîner manuellement sur la plateau. Pour cela vous pouvez sélectionner un fichet en cliquant dessus, (clic gauche) ceci aura pour effet de transformer le curseur de la souris en fichet. Pour déplacer le fichet, maintenir le bouton de la souris pressé, bouger la souris jusquà ce que le curseur se trouve au dessus d'une case jouable, puis relâcher le bouton de la souris.

De la même manière, vous pouvez sélectionner (ou relâcher) un fichet en pressant la barre d'espacement ou la touche Entrée. Ceci a pour effet de sélectionner le fichet sous lequel se trouve le curseur de la souris, ou de déposer le fichet sur une case jouable... Si vous gagnez, la boîte de dialogue I'm so great apparaît, et vous pouvez revoir tous les coups qui vous ont permis d'atteindre la position finale. Vous pouvez alors sauver cette solution ou charger une configuration présauvegardée.


Lancement de la recherche
Lancer la recherche :

Pour cela, il vous suffit de presser la touche F2, ou plus simplement de cliquer sur le bouton Search. Plusieurs cas se présentent alors. Si le programme trouve une solution, la boîte de dialogue xxx s processing apparaît et vous pouvez parcourir les coups qui mènent à la solution. Le programme peut affirmer aussi qu'il n'y a pas de solution. Plus fréquemment, le programme ne trouvera pas de solution, et indiquera qu'il faut modifier les paramètres de recherche pour connaître s'il y en a une ou s'il n'y en a pas.

Si vous avez poussé la profondeur de recherche au dessus de 10, il se peut que vous n'ayez pas suffisamment de mémoire pour que le calcul s'effectue jusqu'au bout, dans ce cas augmentez la mémoire virtuelle de votre configuration (icône 386 étendu du panneau de configuration) ou achetez de la RAM !

En général, s'il y a une solution, PegSolit saura la trouver avec une profondeur inférieure à 10.

Remarque importante :

PegSolit préfère de loin la configuration :

  ...                             ooo

  ...                             ooo

..o.o..                         ooooooo

ooo.ooo   à la configuration:   ooo.ooo

ooooooo                         ..o.o..

  ooo                              ...

  ooo                              ...

Choisissez la bonne symétrie, sachant qu'il vaut généralement mieux que les fichets soient en bas à droite, plutôt qu'en haut à gauche ! Boutons Rotation (Alt+R ou Ctrl+R) et Mirror (Alt+Y ou Ctrl+S).


Annuler le dernier mouvement
Annuler le dernier mouvement :

Cliquez sur le bouton Back !.

Pressez la touche BackSpace.

Pressez la touche F4.

Si vous possédez une souris 3 boutons, cliquez sur le bouton du milieu, pour revenir au tableau initial.

Pressez Ctrl + flèche gauche pour revenir au tableau initial.

Attention, si vous positionnez un fichet en cliquant sur le bouton de droite de la souris, vous annulez l'historique. Même effet si vous choisissez une configuration de départ, ou si vous videz le plateau.


Abandonner la recherche
Abandonner la recherche :

Cliquez sur le bouton Abort. Attention, si vous désirez quitter PegSolit™ (touche Alt+F4, bouton Exit, ou activation du menu système + Fermeture) vous devez préalablement abandonner la recherche, s'il y en a une en cours.


Modification des paramètres
Modifier les paramètres :

La touche F3 lance la boîte de dialogue en question.

Cliquez sur le bouton Options.

Vous pouvez modifier la profondeur de recherche. Attention, pour des profondeurs conséquentes (plus de 10), le temps de recherche s'accroît considérablement. Par défaut la profondeur est de 0. (Cette valeur savère suffisante pour les cas classiques des Solitaires anglais et français). Malheureusement, elle se révèle insuffisante pour trouver une solution (ou affirmer qu'il n'y en a pas) pour des cas beaucoup plus élaborés. Vous devez alors augmenter cette valeur, et patienter un peu plus pour enfin, peut être, connaître une solution.

Vous avez aussi la possibilité de modifier le mode d'élagage effectué par le programme (Grosso modo, le programme rejette les configurations dans lesquels il existe un fichet isolé, cela s'avère efficace dans la majorité des cas, mais il existe des cas pour lesquels il ne doit pas y avoir d'élagage pour trouver une solution).

Exemple :

  ...

  o..

.......

...oo..

..o....

  ...

  ...

Cette configuration sera éliminée(*) dans le mode deep pruning, car le fichet du dessus est considéré comme isolé du reste du jeu. En revanche, si vous lancez la recherche dans le mode low pruning, la solution sera trouvée.

(*) Par ailleurs si vous partez d'une configuration ayant moins de 12 fichets, le programme n'élaguera pas, ce qui évite, en fait, les cas comme celui présenté en exemple.

Cliquez sur la touche Look, pour modifier laspect du tableau et des fichets.

Cliquez sur la touche Solved, pour visualiser les tableaux sauvegardés.

Le dessin final positions indique les emplacements possible  pour le dernier pion s'il y a une solution.

en rouge : positions finales.


Remarques particulières
Remarques particulières :

Sur un 386 DX 25 Mhz, 4 Mo de RAM (Configuration sur laquelle a été conçue l'application), la résolution du Solitaire anglais, classique, met 10s avec une profondeur de 0. La résolution du Solitaire français met 12s, avec la même profondeur. (Tout cela avec un élagage massif). Pour les Solitaires égyptien et aztèque, tout dépend de la case que vous enlevez au départ, le temps varie entre 5 et 30 secondes. J'ai joins au fichier zippé plusieurs fichiers .pgs qui contiennent des sauvegardes de cas classiques, que les joueurs de Solitaire connaissent bien. Vous pouvez les charger pour connaître les solutions et les temps de recherche (courts !) sur mon OLD-PC.

J'ignore si le Solitaire aztèque est commercialisé. Il présente la particularité (frustrante !) d'être insoluble si l'on enlève au départ, comme unique fichet, le fichet central. (Eh oui ! comme les Solitaires français et hexa !).

Dans une prochaine version, je vais tâcher d'implanter le Solitaire continental. En vogue aux siècles précédents, mais complètement disparu depuis, il se présentait sous la forme suivante (à gauche). Le Solitaire à droite est une croix (Solitaire anglais étendu aux quatre points cardinaux) que j'implanterai facilement par la même occasion (connu aussi sous le nom de Solitaire de Wiegleb).

Il ne m'apparaît pas vraiment intéressant de laisser à l'utilisateur la possibilité de créer ses propres tableaux "mères".

Si le côté programmation vous intéresse, voici quelques remarques sur l'algorithme de résolution.

Si vous avez des remarques particulières, voici mon adresse postale.

PHILIPPE BASCIANO, 20 janvier 1996, 21h30.


Recette de l'application
Recette de l'application ou quelques remarques sur l'algorithme

En résumé, je crois que la recette de l'application tient en trois points importants :

1) Utilisation d'un compilateur très performant.

2) Un algorithme "bourrin" mais efficace.

3) Un stockage des données privilégiant la rapidité à la place mémoire utilisée.


Utilisation d'un Compilateur très performant.

Je suis à l'heure actuelle (octobre 1995) en troisième année d'école d'ingénieurs (ESIAL). Dans un premier temps, j'ai réalisé ce logiciel en EIFFEL (un langage à objets utilisé principalement dans un but pédagogique). Il s'agissait en fait d'un TP donné en licence d'informatique [et en première année ESIAL]. Ensuite, par intérêt personnel, j'ai décidé de le "porter" en C, puis d'écrire une interface graphique sous Windows. (en fait pegresol.exe a été compilé depuis un source C, et pegsolit.exe provient d'un source Pascal Objet (TPW 1.5)).

J'ai d'abord développé le moteur de recherche pegresol.c sous UNIX (compilé avec GNU C). Le résultat obtenu était assez encourageant. Lors du portage sur P.C., ce même source compilé avec Borland C++ 3.1 m'a beaucoup déçu, en fait la gestion de la mémoire, les allocations dynamiques, les fonctions malloc, free ... sont bien pauvrement implantées par Borland. L'application échouait dès qu'il s'agissait de résoudre une configuration ayant plus de 10 pions!

L'exécutable actuel a été compilé avec le "Optimizing Watcom C" (licence du compilo appartenant à l'université UHP-Nancy I) qui reste sans aucun doute à l'heure actuelle le meilleur compilateur C (32 bits) sur plateforme DOS/Windows. (Certains s'engagent à dire qu'il s'agit bel et bien du meilleur compilateur tout court. Et mon expérience personnelle tendrait à le confirmer). En clair, si le Watcom C n'existait pas je n'aurais jamais pu obtenir un exécutable qui tienne la route sous Windows !

Voilà pour les outils de compilation. En ce qui concerne l'algorithme, le cadre du TP scolaire était la récursivité avec back-tracking, mon premier source Eiffel implantait donc cette technique de résolution. Elle s'avère en fait bien inefficace, on peut difficilement tenir compte des doubles, des symétries ...


Un Algorithme "bourrin" mais efficace.

L'algorithme implanté est ici la création itérative de "niveaux".

Le niveau 0 contient le solitaire à résoudre.

Le niveau 1 contient tous les solitaires obtenus à partir du solitaire du niveau 0, en effectuant un seul déplacement.

Le niveau (k+1) contient tous les solitaires obtenus à partir des solitaires du niveau k, en effectuant un seul déplacement.

Si le solitaire du niveau 0 contient p pions, celui du niveau k en contient (p-k). On s'arrête donc au niveau (p-1). (et déduction du résultat...).

Pour optimiser, on élimine à chaque niveau tous les symétriques (il y en a 7 pour un plateau donné). Malgré ces éliminations, si on ne limitait pas le nombre de solitaires par niveau, on dépasserait très rapidement les capacités mémoire de l'ordinateur. D'où l'introduction d'une limite (Depth dans le programme). Dès qu'un niveau contient plus de solitaires que la limite fixée, on passe au niveau suivant).

Pour information,

depth=0 correspond à une limite de 90 configurations

depth=1 correspond à une limite de 590 configurations

depth=2 correspond à une limite de 1090 configurations

depth=3 correspond à une limite de 1590 configurations

... etc. ...

depth=k correspond à une limite de 500*k+90 configurations

Une deuxième optimisation consiste à éliminer les solitaires ayant 1 pion isolé. Cette deuxième optimisation est moins efficace que la première.


Stockage des données privilégiant la rapidité à la place mémoire utilisée.

Pour stocker un solitaire, on code 1 ligne par 1 octet ! (en fait on a un bit inutilisé !). Le solitaire comporte 7 lignes, d'où pour stocker 1 solitaire il faut 7 octets. Il y a moyen de n'utiliser que 5 octets, en ne stockant pas les cases inutilisées. En fait seuls 29 bits suffisent car les invariants de De Brujin déterminent 4 cases, si les 29 autres sont déjà fixées ! Mais cette dernière implantation, même si elle présente l'avantage de stocker 1 tableau sur 1 entier de 32 bits, reste cependant maladroite.

Le choix d'une bonne implantation pour le stockage des solitaires à chaque niveau est apparu crucial. Dans un premier temps, j'ai utilisé une seule liste chaînée (triée). Lors du remplissage d'un niveau, on insère les solitaires dans la liste en fonction de la valeur des 7 octets de données.

Pour insérer un solitaire, il faut parcourir la liste chaînée en comparant à chaque fois les 7 (en fait un peu moins car la fonction "and" est optimisée !) octets de données du solitaire à insérer avec les solitaires de la liste. Cette implantation est en fait malheureuse, car il faut beaucoup d'opérations pour insérer un solitaire ou pour tester si un solitaire est déjà présent dans un niveau, et donc forcément, beaucoup de temps. (pour les solitaires aztèque, égyptien et hexa, cette implantation suffit).

Pour finir, j'ai décidé d'implanter le stockage des solitaires sous la forme d'un arbre n-aire: chaque noeud de l'arbre étant une ligne du solitaire. Cette solution a l'inconvénient de nécessiter beaucoup de place mémoire, mais en revanche, très peu d'opérations sont nécessaires pour insérer un solitaire dans l'arbre (ou pour tester la présence), et donc le temps de recherche est considérablement réduit !


Sauver, Charger une configuration précalculée.
Sauvegarder, Charger une solution.

Lorsque la boîte de dialogue I'm so great ou xxx s processing apparaît, vous cliquez sur le bouton Save ou Load. Si vous désirez accéder directement à cette boîte pour charger une solution, positionnez deux fichets côte à côte sur un tableau vide et lancez la recherche !

Attention, vous ne pouvez charger que des tableaux classiques (français ou anglais) si vous venez de résoudre un tableau classique, de même pour un tableau égyptien ou aztèque ...

Exemple de fichier de sauvegarde :

[CAPTION]

; Ce message s'affiche sur la barre de la boîte de dialogue

message=1s processing.

[SETTINGS]

; Genre (2=Français)

Kind=2

; nombre de pions sur le tableau - 1

nb=5

; profondeur de recherche (absolue)

Depth=90

; Mode d'élagage (2 = deep)

Pruning=2

[BOARDS]

; Les tableaux

0=00000000023414

1=00000000020C14

2=00000000060810

3=00000000080810

4=00000000000018

5=00000000000004


Les afficheurs numériques
Les afficheurs numériques.

Coin haut gauche : Nombre de fichets sur le tableau.

Coin haut droite : Nombre de coups jouables.

Coin bas gauche : m, la première somme de De Brujin.

Coin bas droite : n, la deuxième somme de De Brujin.

Les sommes de De Brujin sont des invariants i.e. des valeurs qui restent inchangées si vous déplacez un fichet quelconque sur le plateau, du moment que le coup est licite. Sachant que ces sommes ne valent jamais 0, pour un unique fichet (placé n'importe où sur les plateaux français ou anglais), si vous partez d'un tableau dont une des sommes vaut 0, alors on peut affirmer dès le départ qu'il n'y a pas de solution. En revanche, la réciproque est totalement fausse, vous pouvez disposer deux fichets (qui ne soient pas l'un près de l'autre) sur le plateau et qui soient positionnés de telle façon qu'aucune des deux sommes ne soient nulle.

Ex :

  ...

  ...

..o....

....... (Dans ce cas n=2, m=3 mais il n'y a pas de solution).

..o....

  ...

  ...

Pour les petits programmeurs et les petits mathématiciens intéressés, voici le code, simplifié, et traduit en Pascal, que j'ai implanté pour calculer ces sommes (valide dans le cas des solitaires classiques) :

CONST bs_table = 6; {nb de cases - 1}

TYPE Solitaire = ARRAY[0..bs_table,0..bs_table] OF BOOLEAN;

{un tableau de cases}

{(i,j) pleine ssi A[i,j]}

CONST _plusG4 : ARRAY[0..3,0..3] OF BYTE {Addition dans le Groupe G4}

= ((0,1,2,3),

   (1,0,3,2),

   (2,3,0,1),

   (3,2,1,0));

FUNCTION De_Brujin_N(A : Solitaire) : BYTE; {Somme n}

VAR i,j : BYTE;

    som : BYTE;

BEGIN

 som := 0;

 FOR i := 0 TO bs_table DO

  FOR j := 0 TO bs_table DO

   IF (A[i,j]) THEN som := _plusG4[som,((i+j+2)MOD 3)+1];

 De_Brujin_N := som;

END;

FUNCTION De_Brujin_M(A : Solitaire) : BYTE; {Somme m}

VAR i,j : BYTE;

    som : BYTE;

BEGIN

 som := 0;

 FOR i := 0 TO bs_table DO

  FOR j := 0 TO bs_table DO

   IF (A[i,j]) THEN som := _plusG4[som,((i-j+6)MOD 3)+1];

 De_Brujin_M := som;

END;


Mon adresse postale
Basciano Philippe

46 rue de Cornouaille

22000 Saint-Brieuc

France


Remerciements
Remerciements !

LGT, mon (grand) binôme de 1ère 2ème, 3ème années d'ESIAL ... ouaip' ... faut bien commencer par lui. Pour tout le temps que j'aurai passé à programmer ce (petit) jeu ridicule au lieu de participer activement aux TPs (chuuutttt !!!). CHRISTOPHE MAGIN PRIART, pour son article paru dans le Pascalissime de la période Avril-Juin 1994. MOK, pour ses plans Café au Mc Draw de Vandoeuvre, à 23h15. ... eh eh eh eh ... wreuseukteufeu ... VILYAM, pour ses plans Pizzas au Best Of le vendredi soir et Mc Do le samedi soir, ... eh eh eh eh ... Au fait,  t'as fait quoi de tes vacances, Basting' ? T'es allé en Bretagne ? Où ça ? A Plélan-Le-Grand ? VOUVOULLE, the Basic Chris Waddle Fan, pour ses plans Be Hap , Batchi, Petites Bouteilles, Campus, Métro, Anthéa et Bar Techno qui m'ont beaucoup inspiré (perturbé ?) pour la création de ce jeu. Putain plus qu'un mois à Nancy ... [ndla 4/3/1996]. PROTO, PROTO Light, PROTO Light Light Light, pour avoir embelli par leur simple présence tous mes samedis soirs. Tous les gens qui ont aimé mes autres jeux, en particulier Fructus, pour lequel j'ai dû recevoir à cette date une centaine de cartes postales du monde entier !. PATRICE L. (Dont les lectures, Le Clézio en particulier ..., m'ont beaucoup influencé). Sszzuuuuttt, j'ai oublié les autres, ... à oui DUDU ... qui aurait joué un peu avec la première version de ce programme ... PH, BENOIT, LOIC et les autres, qui n'ayant pas aimé ma première version m'ont fait prendre pleinement conscience de ses limites ! (en espérant que celle-ci leur plaira davantage) ... et pis de toute façon on s'en fout y'a ce putain de TP compilo (Eiffel caca) à finir, ce TP malg (Caml-Sml caca), et pis tous les partiels de Juin à réviser en particulier la B.D. et la Gestion ...

(>> Septembre !!! <<)


Next !
Sorry !

Under construction !

Perhaps it will be implemented in further versions of Peg Solitaire !

If you have good skills in translation, please let me know !


Sorry Loïc !
Désolé Loïc, j'ai eu beau essayer n fois,

Morrissey et les Smiths, ben j'aime pas ...


Bibliographie sélective
Bibliographie sélective (Selective bibliography) :

The ins and outs of Peg Solitaire, John D. Beasley, Oxford University Press.

La mathématique des jeux, article de Pierre Tougne, Bibliothèque Pour la Science.

Traité du jeu du Solitaire, J. Cabrera et R. Hout, éditions Flammarion, 1977.

Récréations mathématiques, Tome I, E.Lucas, éditions Blanchard 1977.

Winning ways, Tomes I et II, E. Berlekamp, J. Conway, R. Guy, Academic Press, 1982.

You can also have a look at the rec.puzzles newsgroup on Internet for interesting related problems.

Other Peg Solitaire games for Windows :


Bref historique du jeu
Bref historique du jeu :

Les Romains ont connu un jeu de patience pratiqué sur une table dotée de cavités où l'on déplaçait des boules.

En France, au moyen-âge, existaient de petits plateaux ronds pourvus de trous recevant des billes.

Le jeu pratiqué aujourd'hui remonte au début du XVIIème siècle. La tradition en attribue l'invention à Pellisson embastillé par Louis XIV.

Selon d'autres, un voyageur aurait rapporté ce jeu pratiqué par des indiens en Amérique.

Extait d'un ouvrage "Le Backgammon et le Solitaire" ...


ESIAL
ESIAL :

Ben c'est une petite école d'ingénieurs

de l'université Henri Poincaré Nancy I ...


This is a turtle ....


Gôbeuse !!!!!!!!!!!!!!!!!!!!!!!!!!


Putain ce bombeur orange !!!!!!!!!!!!!!!!!